#include "../interface/T_gl_SpatialTree.h"
#include "../rtCommon/Intersect.h"

#define HISTOGRAM_BIN 1024

void C_gl_SpatialTree::ActorData(int nCount, I_api_Device *pDevice)
{
	if (m_pActorData == NULL) m_pActorData = new T_Buffer_GL<float4>();
	m_pActorData->Create(nCount, pDevice);
}

void C_gl_SpatialTree::KdTree(I_api_Device * pDevice, int nMaxDepth, int nCount)
{
	m_nDepth = nMaxDepth;
	if (m_pKdTree == NULL) m_pKdTree = new T_Buffer_GL<S_KdNode>();
	m_pKdTree->Create(((1<<(m_nDepth+1))-1) * nCount, pDevice);
}

void C_gl_SpatialTree::BVHTree(I_api_Device * pDevice, int nMaxDepth, int nCount)
{
	m_nDepth = nMaxDepth;
	if (m_pBVHTree == NULL) m_pBVHTree = new T_Buffer_GL<S_BVHNode>();
	m_pBVHTree->Create(((1<<(m_nDepth+1))-1) * nCount, pDevice);
}


void C_gl_SpatialTree::KdTree(I_SpatialTree * pShared, int nMaxDepth, int nCount)
{
	m_nDepth = nMaxDepth;
	if (m_pKdTree == NULL) m_pKdTree = new T_Buffer_GL<S_KdNode>();
	m_pKdTree->Create(((1<<(m_nDepth+1))-1) * nCount, pShared->KdTree());
}

void C_gl_SpatialTree::BVHTree(I_SpatialTree * pShared, int nMaxDepth, int nCount)
{
	m_nDepth = nMaxDepth;
	if (m_pBVHTree == NULL) m_pBVHTree = new T_Buffer_GL<S_BVHNode>();
	m_pBVHTree->Create(((1<<(m_nDepth+1))-1) * nCount, pShared->BVHTree());
}

void C_gl_SpatialTree::Create(int nFlag, 
														  I_Buffer *pVertex, 
															I_Buffer *pIndex,
															int nVertex, int nPrimitive, 
															int nCount, int nDepth,
															I_api_Device * pDevice)
{
	m_nVertex = nVertex;
	m_nPrimitive = nPrimitive;
	m_nDepth = nDepth;

	if (pVertex != NULL && pIndex != NULL){
		m_pVertex = pVertex;
		m_pIndex = pIndex;
	}

	if (nFlag & e_SpatialTree_Data_PrimitiveBI)
	{
		for (uint32 iAxis = X; iAxis < XYZ; iAxis++)
		{
			if (m_ppBoundingInterval[iAxis] == NULL) m_ppBoundingInterval[iAxis] = new T_Buffer_GL<float2>();
			m_ppBoundingInterval[iAxis]->Create(nPrimitive, pDevice);
		}
	}

	if (nFlag & e_SpatialTree_Data_PrimIdx) {
		if (m_pPrimIdx == NULL) m_pPrimIdx = new T_DoubleBuffer_GL<int>();
		m_pPrimIdx->Create(nPrimitive * 16, pDevice);
	}

	if (nFlag & e_SpatialTree_Data_WeightStart) {
		if (m_pActorData == NULL) m_pActorData = new T_Buffer_GL<float4>();
		m_pActorData->Create(nPrimitive, pDevice);
	}

	if (nFlag & e_SpatialTree_Data_TreeIdx) {
		if (m_pTreeIdx == NULL) m_pTreeIdx = new T_Buffer_GL<int>();
		m_pTreeIdx->Create(nPrimitive * 16, pDevice);
	}

	if (nFlag & e_SpatialTree_Data_Interval) {
		if (m_pInterval == NULL) m_pInterval = new T_Buffer_GL<float2>();
		m_pInterval->Create (XYZ*((1<<(m_nDepth+1))-1), pDevice);
	}

	if (nFlag & e_SpatialTree_Data_Node) {
		if (m_pNode == NULL) m_pNode = new T_Buffer_GL<float4>();
		m_pNode->Create((1<<(m_nDepth+1))-1, pDevice);
	}

	if (nFlag & e_SpatialTree_Data_Kd) KdTree(pDevice, nDepth, nCount); 
	if (nFlag & e_SpatialTree_Data_BVH)	BVHTree(pDevice, nDepth, nCount); 
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::Create(int nFlag, 
															I_Buffer *pVertex, 
															I_Buffer *pIndex,
															int nVertex, int nPrimitive, 
															int nCount, int nDepth,
															I_SpatialTree * pShared)
{
	m_nVertex = nVertex;
	m_nPrimitive = nPrimitive;
	m_nDepth = nDepth;

	if (pVertex != NULL && pIndex != NULL){
		m_pVertex = pVertex;
		m_pIndex = pIndex;
	}

	if (nFlag & e_SpatialTree_Data_PrimitiveBI)
	{
		for (uint32 iAxis = X; iAxis < XYZ; iAxis++) 
			m_ppBoundingInterval[iAxis] = pShared->m_ppBoundingInterval[iAxis];
	}

	if (nFlag & e_SpatialTree_Data_PrimIdx) 
		m_pPrimIdx = pShared->m_pPrimIdx;

	if (nFlag & e_SpatialTree_Data_TreeIdx) {
		if (m_pTreeIdx == NULL) m_pTreeIdx = new T_Buffer_GL<int>();
		m_pTreeIdx->Create(nPrimitive * 16, pShared->m_pTreeIdx);
	}

	if (nFlag & e_SpatialTree_Data_Interval) m_pInterval = pShared->m_pInterval; 
	if (nFlag & e_SpatialTree_Data_Node) m_pNode = pShared->m_pNode; 

	if (nFlag & e_SpatialTree_Data_Kd) KdTree(pShared, nDepth, nCount); 
	if (nFlag & e_SpatialTree_Data_BVH) BVHTree(pShared, nDepth, nCount); 
}

void C_gl_SpatialTree::PrimitiveAABB()
{
	int3 i;

	float2 * pBoundingIntervalX = (float2 *) m_ppBoundingInterval[X]->hPtr();
	float2 * pBoundingIntervalY = (float2 *) m_ppBoundingInterval[Y]->hPtr();
	float2 * pBoundingIntervalZ = (float2 *) m_ppBoundingInterval[Z]->hPtr();

	if (m_pIndex != NULL && m_pVertex != NULL)
	{
		T_idx * pIndex = (T_idx *) m_pIndex->hPtr();
		T_pos * pVertex = (T_pos *) m_pVertex->hPtr();

		m_Box.pmax = f3(pVertex[0].x, pVertex[0].y, pVertex[0].z);
		m_Box.pmin = f3(pVertex[0].x, pVertex[0].y, pVertex[0].z);

		for (int iVertex = 1; iVertex < nVertex(); iVertex++){
			m_Box.pmax = max(m_Box.pmax, f3(pVertex[iVertex].x, pVertex[iVertex].y, pVertex[iVertex].z));
			m_Box.pmin = min(m_Box.pmin, f3(pVertex[iVertex].x, pVertex[iVertex].y, pVertex[iVertex].z));
		}

		for (int iPrim = 0; iPrim < nPrimitive(); iPrim++)
		{
			i.x = pIndex[iPrim*3+0];
			i.y = pIndex[iPrim*3+1];
			i.z = pIndex[iPrim*3+2];

			float3 v0 = f3(pVertex[i.x]);
			float3 v1 = f3(pVertex[i.y]);
			float3 v2 = f3(pVertex[i.z]);

			float3 mn = min(min(v0, v1), v2);
			float3 mx = max(max(v0, v1), v2);

			pBoundingIntervalX[iPrim] = f2(mn.x, mx.x);
			pBoundingIntervalY[iPrim] = f2(mn.y, mx.y);
			pBoundingIntervalZ[iPrim] = f2(mn.z, mx.z);
		}
	}
	else
	{
		m_Box.pmin = f3(pBoundingIntervalX[0].x, pBoundingIntervalY[0].x, pBoundingIntervalZ[0].x);
		m_Box.pmax = f3(pBoundingIntervalX[0].y, pBoundingIntervalY[0].y, pBoundingIntervalZ[0].y);

		for (int iPrim = 1; iPrim < nPrimitive(); iPrim++)
		{
			m_Box.min( f3(pBoundingIntervalX[iPrim].x, pBoundingIntervalY[iPrim].x, pBoundingIntervalZ[iPrim].x) );
			m_Box.max( f3(pBoundingIntervalX[iPrim].y, pBoundingIntervalY[iPrim].y, pBoundingIntervalZ[iPrim].y) );
		}
	}
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

bool C_gl_SpatialTree::SearchSplit(float2 **ppPrimBI, 
																	 T_idx *pPosIdx,
																	 int nCount, 
																	 S_Interval *pInterval,
																	 int & axis, 
																	 int & sah_bin, 
																	 S_TreeNode & s)
{
	const int nBin = HISTOGRAM_BIN;
	int2 Bin[nBin+1];
	int2 Scan[nBin+1];
	int iBin = 0;

	float oldSah = 0.0f, newSah = 0.0f;

	S_Box box;
	AABox(&box, (float2 *) pInterval);

	float surface = Surface(box);
	float inv_surface = 1.0f / surface;

	float Ct = 1.0f, Cb = 1.0f;

	oldSah = nCount * Ct + Cb;

	for (int iAxis = X; iAxis < XYZ; iAxis++)
	{
		for (iBin = 0; iBin <= nBin; iBin++){
			Bin[iBin] = i2();
			Scan[iBin] = i2();
		}

		S_Interval interval = pInterval[iAxis];

		float l = interval.length();
		float step = l / nBin;

		for (int iPrim = 0; iPrim < nCount; iPrim++)
		{
			int BoundingIntervalIdx = pPosIdx[iPrim];
			float2 bi = ppPrimBI[iAxis][BoundingIntervalIdx];

			iBin = max(0, (int) ((bi.x - interval.start) / l * (nBin)));
			Bin[iBin].x++;

			iBin = min(nBin-1, (int)((bi.y - interval.start) / l * (nBin)));
			Bin[iBin].y++;
		}

		for (iBin = 1; iBin <= nBin; iBin++) Scan[iBin] = Scan[iBin-1] + Bin[iBin-1];
		for (iBin = 0; iBin <= nBin; iBin++) Scan[iBin].y = Scan[nBin].y - Scan[iBin].y;

		for (iBin = 1; iBin < nBin-1; iBin++)
		{
			S_Box leftBox, rightBox;

			float splitPoint = interval.start + step * iBin;

			leftBox  = box;
			rightBox = box;

			((float *)&( leftBox.pmax))[iAxis] = splitPoint; // change pmax for left box 
			((float *)&(rightBox.pmin))[iAxis] = splitPoint; // and    pmin for rght box

			float leftSAH  = (Ct * Scan[iBin].x) * Surface(leftBox);
			float rightSAH = (Ct * Scan[iBin].y) * Surface(rightBox);

			newSah = (leftSAH + rightSAH) * inv_surface + Cb*2;

			/// Check is newSAH is better cmpd to oldSAH
			if (newSah < oldSah)
			{
				oldSah = newSah;
				s.split = splitPoint;
				s.sah = newSah;
				axis = iAxis;
				sah_bin = iBin;

				/// Save how many elements go into each subtree
				s.left = Scan[iBin].x;
				s.right = Scan[iBin].y;
			}
		}
	}

	return axis != TREE_LEAF;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

bool C_gl_SpatialTree::SearchSplit(float2 **ppPrimBI,
																	 float4	*pWeight,
																	 T_idx *pPosIdx,
																	 int nCount, 
																	 int nWeight,
																	 S_Interval *pInterval,
																	 int & axis, 
																	 int & sah_bin, 
																	 S_TreeNode & s)
{
	const int nBin = HISTOGRAM_BIN;
	int2 Bin[nBin+1];
	int2 Scan[nBin+1];
	int iBin = 0;

	float oldSah = 0.0f, newSah = 0.0f;

	S_Box box((float2*)pInterval);

	float surface = Surface(box);
	float inv_surface = 1.0f / surface;

	float Ct = 1.0f, Cb = 1.0f;

	oldSah = nWeight * Ct + Cb;

	for (int iAxis = X; iAxis < XYZ; iAxis++)
	{
		for (iBin = 0; iBin <= nBin; iBin++){
			Bin[iBin] = i2();
			Scan[iBin] = i2();
		}

		S_Interval interval = pInterval[iAxis];

		float l = interval.length();
		float step = l / nBin;

		for (int iPrim = 0; iPrim < nCount; iPrim++)
		{
			int BoundingIntervalIdx = pPosIdx[iPrim];
			float2 bi = ppPrimBI[iAxis][BoundingIntervalIdx];

			iBin = max(0, (int) ((bi.x - interval.start) / l * (nBin)));
			Bin[iBin].x+=pWeight[BoundingIntervalIdx].x;

			iBin = min(nBin-1, (int) ((bi.y - interval.start) / l * (nBin)));
			Bin[iBin].y+=pWeight[BoundingIntervalIdx].x;
		}

		for (iBin = 1; iBin <= nBin; iBin++) Scan[iBin] = Scan[iBin-1] + Bin[iBin-1];
		for (iBin = 0; iBin <= nBin; iBin++) Scan[iBin].y = Scan[nBin].y - Scan[iBin].y;

		for (iBin = 1; iBin < nBin-1; iBin++)
		{
			S_Box leftBox, rightBox;

			float splitPoint = interval.start + step * iBin;

			leftBox  = box;
			rightBox = box;

			((float *)&( leftBox.pmax))[iAxis] = splitPoint; // change pmax for left box 
			((float *)&(rightBox.pmin))[iAxis] = splitPoint; // and    pmin for rght box

			float leftSAH  = (Ct * Scan[iBin].x) * Surface(leftBox);
			float rightSAH = (Ct * Scan[iBin].y) * Surface(rightBox);

			newSah = (leftSAH + rightSAH) * inv_surface + Cb*2;

			/// Check is newSAH is better cmpd to oldSAH
			if (newSah < oldSah)
			{
				oldSah = newSah;
				s.split = splitPoint;
				s.sah = newSah;
				axis = iAxis;
				sah_bin = iBin;
				s.left = Scan[iBin].x;
				s.right = Scan[iBin].y;
			}
		}
	}

	return axis != TREE_LEAF;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::KdTree_p0()
{
	/// First init index array for root
	int * pTreeIdx  = (int *) m_pTreeIdx->hPtr();
	float2 * ppBI[XYZ]	=	{	(float2 * ) m_ppBoundingInterval[X]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Y]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Z]->hPtr() };
	
	int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
	for (int32 iPrim = 0; iPrim < nPrimitive(); iPrim++) pPrimIdxR[iPrim] = iPrim;

	/// Init Root Node
	m_nNode = m_nPrimIdx = m_nTreeIdx = m_nInterval = 0;

	/// Take Root Node and insert it into the BuildTree Node Tree
	S_TreeNode root(m_nPrimIdx, nPrimitive());

	S_TreeNode *pTree = (S_TreeNode *) m_pNode->hPtr();
	pTree[m_nNode++] = root;

	S_Interval *pInterval = (S_Interval *) m_pInterval->hPtr();
	pInterval[m_nInterval++] = f2(m_Box.pmin.x, m_Box.pmax.x);
	pInterval[m_nInterval++] = f2(m_Box.pmin.y, m_Box.pmax.y);
	pInterval[m_nInterval++] = f2(m_Box.pmin.z, m_Box.pmax.z);

	/// Get Maximum size of primIdx array
	int nPrimIdxSize = m_pPrimIdx->pBufferR()->Size();

	/// Try to create maxDepth levels of KdTree
	int32 depth = 0;
	int32 leaf_count = 0;
	int32 node_count = 1, node_offset = 0;

	while (depth < m_nDepth && leaf_count != node_count)
	{
		int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
		int * pPrimIdxW = (int *) m_pPrimIdx->hPtrW();

		m_nPrimIdx = 0;	// reset primitive_idx_offset
		leaf_count = 0;	// reset leaf_count 

		node_count = (depth > 0) ? 1 << depth : 1; // this level has this many nodes that require splitting            
		node_offset = ((1 << (depth+1)) - 1) - node_count; // nodes for this level are located starting from this offset    

		for (int32 iNode = 0; iNode < node_count; iNode++)
		{
			int32 current_node_index = node_offset + iNode;

			S_TreeNode current_node = pTree[current_node_index];

			int32   primitive_count = current_node.end - current_node.start;

			if ((m_nTreeIdx+m_nPrimIdx+primitive_count*2 < nPrimIdxSize) && !current_node.Leaf())
			{							
				S_Interval * pCurInterval = pInterval + current_node_index*XYZ;

				S_TreeNode s;

				int32 axis = TREE_LEAF;
				int32 bin = 0;

				if (primitive_count > m_nMaxPrim && (depth+1<m_nDepth) && SearchSplit(ppBI, pPrimIdxR + current_node.start, primitive_count, pCurInterval, axis, bin, s))
				{
					/// For current Node set splitting plane
					pTree[current_node_index].SplitAxis(s.split, axis);
					pTree[current_node_index].left  = m_nNode;   
					pTree[current_node_index].right = m_nNode+1;

					int32 indexLeft = m_nPrimIdx;
										
					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];							

						if (PrimitiveBI.x <= s.split) pPrimIdxW[indexLeft++] = PrimitiveIndex;
					}

					int32 indexRight = indexLeft;

					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];						

						if (PrimitiveBI.y > s.split) pPrimIdxW[indexRight++] = PrimitiveIndex;
					}
					S_TreeNode left_node(m_nPrimIdx, indexLeft, current_node_index);					
					S_TreeNode right_node(indexLeft, indexRight, current_node_index);

					pTree[m_nNode++] = left_node;
					pTree[m_nNode++] = right_node;

					pTree[current_node_index].SplitAxis(s.split, axis);

					/// Make Left and Right Intervals and insert them into intervalTree
					S_Interval left_interval[XYZ], right_interval[XYZ];

					// copy node interval into left_interval
					left_interval[X] = pCurInterval[X]; 
					left_interval[Y] = pCurInterval[Y]; 
					left_interval[Z] = pCurInterval[Z]; 
					// copy node interval into right_interval
					right_interval[X] = pCurInterval[X]; 
					right_interval[Y] = pCurInterval[Y]; 
					right_interval[Z] = pCurInterval[Z]; 

					// modify left & right ends of interval on split axis
					pTree[current_node_index].SplitAxis(s.split, axis);
					left_interval[axis].end = s.split;
					right_interval[axis].start = s.split; 

					pInterval[m_nInterval++] = left_interval[X];
					pInterval[m_nInterval++] = left_interval[Y];
					pInterval[m_nInterval++] = left_interval[Z];
					pInterval[m_nInterval++] = right_interval[X];
					pInterval[m_nInterval++] = right_interval[Y];
					pInterval[m_nInterval++] = right_interval[Z];

					m_nPrimIdx += left_node.Count() + right_node.Count();
				}
				else
				{
					pTree[current_node_index].start = m_nTreeIdx;
					pTree[current_node_index].end   = m_nTreeIdx + primitive_count;
					pTree[current_node_index].SplitAxis(0.0f, TREE_LEAF);

					S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

					pTree[m_nNode++] = dummy_node; // left  child dummy
					pTree[m_nNode++] = dummy_node; // right child dummy

					for (int iInterval = 0; iInterval < 6; iInterval++)
						pInterval[m_nInterval++] = S_Interval();

					for (int iTreeIdx = current_node.start; iTreeIdx < current_node.end; iTreeIdx++)
						pTreeIdx[m_nTreeIdx++] = pPrimIdxR[iTreeIdx];

					leaf_count++; // if all nodes kick this line - next depth will not be checked
				} // if (primitive_count > 4 && SAH(EXEC_H, pInterval + current_node_index*XYZ, s, primitive_count))
			} // if ((m_nTree+m_nPrimitive+primitive_count*2 < maxPrim) && !current_node.Leaf())
			else 
			{			
				S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

				pTree[m_nNode++] = dummy_node; // left  child dummy
				pTree[m_nNode++] = dummy_node; // right child dummy

				for (int iInterval = 0; iInterval < 6; iInterval++)
					pInterval[m_nInterval++] = S_Interval();

				leaf_count += 1; // if all nodes kick this line - next depth will not be checked
			}
		} // for (uint32 iNode = 0; iNode < node_count; iNode++)
		m_pPrimIdx->Swap();

		depth++; // increase depth level
	} // while (depth < m_nMaxDepth)
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::KdTree_Instanced_p0()
{
	/// First init index array for root
	int * pTreeIdx  = (int *) m_pTreeIdx->hPtr();
	float2 * ppBI[XYZ]	=	{	(float2 * ) m_ppBoundingInterval[X]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Y]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Z]->hPtr() };

	int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
	for (int32 iPrim = 0; iPrim < nPrimitive(); iPrim++) pPrimIdxR[iPrim] = iPrim;

	/// Init Root Node
	m_nNode = m_nPrimIdx = m_nTreeIdx = m_nInterval = 0;	

	/// Take Root Node and insert it into the BuildTree Node Tree
	S_TreeNode root(m_nPrimIdx, nPrimitive());

	S_TreeNode *pTree = (S_TreeNode *) m_pNode->hPtr();
	pTree[m_nNode++] = root;

	S_Interval *pInterval = (S_Interval *) m_pInterval->hPtr();
	pInterval[m_nInterval++] = f2(m_Box.pmin.x, m_Box.pmax.x);
	pInterval[m_nInterval++] = f2(m_Box.pmin.y, m_Box.pmax.y);
	pInterval[m_nInterval++] = f2(m_Box.pmin.z, m_Box.pmax.z);

	/// Get Maximum size of primIdx array
	int nPrimIdxSize = m_pPrimIdx->pBufferR()->Size();

	/// Try to create maxDepth levels of KdTree
	int32 depth = 0;
	int32 leaf_count = 0;
	int32 node_count = 1, node_offset = 0;

	while (depth < m_nDepth && leaf_count != node_count)
	{
		int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
		int * pPrimIdxW = (int *) m_pPrimIdx->hPtrW();

		m_nPrimIdx = 0; 		// reset primitive_idx_offset
		leaf_count = 0; 		// reset leaf_count 

		node_count = (depth > 0) ? 1 << depth : 1; // this level has this many nodes that require splitting            
		node_offset = ((1 << (depth+1)) - 1) - node_count; // nodes for this level are located starting from this offset    

		for (int32 iNode = 0; iNode < node_count; iNode++)
		{
			int32 current_node_index = node_offset + iNode;

			S_TreeNode current_node = pTree[current_node_index];

			int32	primitive_count = current_node.end - current_node.start;

			if ((m_nTreeIdx+m_nPrimIdx+primitive_count*2 < nPrimIdxSize) && !current_node.Leaf())
			{							
				S_Interval * pCurInterval = pInterval + current_node_index*XYZ;

				S_TreeNode s;

				int32 axis = TREE_LEAF;
				int32 bin = 0;

				if (primitive_count > m_nMaxPrim && (depth+1<m_nDepth) && SearchSplit(ppBI, pPrimIdxR + current_node.start, primitive_count, pCurInterval, axis, bin, s))
				{
					/// For current Node set splitting plane
					pTree[current_node_index].SplitAxis(s.split, axis);
					pTree[current_node_index].left  = m_nNode;   
					pTree[current_node_index].right = m_nNode+1;

					int32 indexLeft = m_nPrimIdx;

					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];							

						if (PrimitiveBI.x <= s.split) pPrimIdxW[indexLeft++] = PrimitiveIndex;
					}

					int32 indexRight = indexLeft;

					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];						

						if (PrimitiveBI.y > s.split) pPrimIdxW[indexRight++] = PrimitiveIndex;
					}
					S_TreeNode left_node(m_nPrimIdx, indexLeft, current_node_index);					
					S_TreeNode right_node(indexLeft, indexRight, current_node_index);

					pTree[m_nNode++] = left_node;
					pTree[m_nNode++] = right_node;

					pTree[current_node_index].SplitAxis(s.split, axis);

					/// Make Left and Right Intervals and insert them into intervalTree
					S_Interval left_interval[XYZ], right_interval[XYZ];

					// copy node interval into left_interval
					left_interval[X] = pCurInterval[X]; 
					left_interval[Y] = pCurInterval[Y]; 
					left_interval[Z] = pCurInterval[Z]; 
					// copy node interval into right_interval
					right_interval[X] = pCurInterval[X]; 
					right_interval[Y] = pCurInterval[Y]; 
					right_interval[Z] = pCurInterval[Z]; 

					// modify left & right ends of interval on split axis
					pTree[current_node_index].SplitAxis(s.split, axis);
					left_interval[axis].end = s.split;
					right_interval[axis].start = s.split; 

					pInterval[m_nInterval++] = left_interval[X];
					pInterval[m_nInterval++] = left_interval[Y];
					pInterval[m_nInterval++] = left_interval[Z];
					pInterval[m_nInterval++] = right_interval[X];
					pInterval[m_nInterval++] = right_interval[Y];
					pInterval[m_nInterval++] = right_interval[Z];

					m_nPrimIdx += left_node.Count() + right_node.Count();
				}
				else
				{
					pTree[current_node_index].start = m_nTreeIdx;
					pTree[current_node_index].end   = m_nTreeIdx + primitive_count;
					pTree[current_node_index].SplitAxis(0.0f, TREE_LEAF); // .split = as_float(KD_LEAF);

					S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

					pTree[m_nNode++] = dummy_node; // left  child dummy
					pTree[m_nNode++] = dummy_node; // right child dummy

					for (int iInterval = 0; iInterval < 6; iInterval++)
						pInterval[m_nInterval++] = S_Interval();

					for (int iTreeIdx = current_node.start; iTreeIdx < current_node.end; iTreeIdx++)
						pTreeIdx[m_nTreeIdx++] = pPrimIdxR[iTreeIdx];

					leaf_count++; // if all nodes kick this line - next depth will not be checked
				} // if (primitive_count > 4 && SAH(EXEC_H, pInterval + current_node_index*XYZ, s, primitive_count))
			} // if ((m_nTree+m_nPrimitive+primitive_count*2 < maxPrim) && !current_node.Leaf())
			else 
			{			
				S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

				pTree[m_nNode++] = dummy_node; // left  child dummy
				pTree[m_nNode++] = dummy_node; // right child dummy

				for (int iInterval = 0; iInterval < 6; iInterval++)
					pInterval[m_nInterval++] = S_Interval();

				leaf_count += 1; // if all nodes kick this line - next depth will not be checked
			}
		} // for (uint32 iNode = 0; iNode < node_count; iNode++)
		m_pPrimIdx->Swap();

		depth++; // increase depth level
	} // while (depth < m_nMaxDepth)
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::BVHTree_p0()
{
	/// First init index array for root
	int * pTreeIdx  = (int *) m_pTreeIdx->hPtr();
	float2 * ppBI[XYZ] = {	(float2 * ) m_ppBoundingInterval[X]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Y]->hPtr(), 
													(float2 * ) m_ppBoundingInterval[Z]->hPtr() };
	
	int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
	for (int iPrim = 0; iPrim < nPrimitive(); iPrim++) pPrimIdxR[iPrim] = iPrim;

	/// Init Root Node
	S_TreeNode root(m_nPrimIdx, nPrimitive());

	m_nNode = 0; 
	m_nPrimIdx = 0;
	m_nTreeIdx = 0;
	m_nInterval = 0;

	S_TreeNode * pTree = (S_TreeNode *) m_pNode->hPtr();
	pTree[m_nNode++] = root;

	S_Interval * pInterval = (S_Interval *) m_pInterval->hPtr();
	pInterval[m_nInterval++] = f2(m_Box.pmin.x, m_Box.pmax.x);
	pInterval[m_nInterval++] = f2(m_Box.pmin.y, m_Box.pmax.y);
	pInterval[m_nInterval++] = f2(m_Box.pmin.z, m_Box.pmax.z);

	/// Get Maximum size of primIdx array
	int nPrimIdxSize = m_pPrimIdx->pBufferR()->Size();

	int32 depth = 0;
	int32 leaf_count = 0;
	int32 node_count = 1, node_offset = 0;

	while (depth < m_nDepth && leaf_count != node_count)
	{
		int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
		int * pPrimIdxW = (int *) m_pPrimIdx->hPtrW();

		m_nPrimIdx = 0; // reset primitive_idx_offset 
		leaf_count = 0; // reset leaf_count 
		
		node_count = (depth > 0) ? 1 << depth : 1;	// this level has this many nodes that require splitting          
		node_offset = ((1 << (depth+1)) - 1) - node_count;	// nodes for this level are located starting from this offset

		for (int32 iNode = 0; iNode < node_count; iNode++)
		{
			int32 current_node_index = node_offset + iNode;
			S_TreeNode current_node = pTree[current_node_index];
			int32	primitive_count = current_node.end - current_node.start;

			if ((m_nTreeIdx+m_nPrimIdx+primitive_count*2 < nPrimIdxSize) && !current_node.Leaf())
			{							
				S_Interval * pCurInterval = pInterval + current_node_index*XYZ;

				S_TreeNode s;
				int32 axis = TREE_LEAF;
				int32 bin = 0;

				if (primitive_count > m_nMaxPrim && (depth+1<m_nDepth) && SearchSplit(ppBI, pPrimIdxR + current_node.start, primitive_count, pCurInterval, axis, bin, s))
				{
					pTree[current_node_index].SplitAxis(s.split, axis);
					pTree[current_node_index].left  = m_nNode;   
					pTree[current_node_index].right = m_nNode+1;

					uint32 indexLeft  = m_nPrimIdx;

					/// Make Left and Right Intervals and insert them into intervalTree
					S_Interval left_interval[XYZ], right_interval[XYZ];						
					left_interval[X] = pCurInterval[X]; 
					left_interval[Y] = pCurInterval[Y]; 
					left_interval[Z] = pCurInterval[Z]; 
					right_interval[X] = pCurInterval[X]; 
					right_interval[Y] = pCurInterval[Y]; 
					right_interval[Z] = pCurInterval[Z];

					// modify left / right ends of interval on split axis
					left_interval[axis].end = s.split; 
					right_interval[axis].start = s.split; 

					// during BVH construction bounding box can be recalculated during primitive sorting					
					bool first = true;
					float2 search_interval[XYZ] = { f2(), f2(), f2() } ;
					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];							
	
						if (PrimitiveBI.x < s.split)
						{
							pPrimIdxW[indexLeft++] = PrimitiveIndex;

							if (first)
							{
								search_interval[0] = ppBI[0][PrimitiveIndex];
								search_interval[1] = ppBI[1][PrimitiveIndex];
								search_interval[2] = ppBI[2][PrimitiveIndex];
								first = false;
							}
							else
							{
								for (int iAxis = 0; iAxis < XYZ; iAxis++)
								{
									search_interval[iAxis].x = min(search_interval[iAxis].x, ppBI[iAxis][PrimitiveIndex].x);
									search_interval[iAxis].y = max(search_interval[iAxis].y, ppBI[iAxis][PrimitiveIndex].y);
								}
							}
						}
					}
					if (!first)
					{
						// but it has to be saturated to the original bounding box
						for (int iAxis = 0; iAxis < XYZ; iAxis++)
						{
							left_interval[iAxis].start = max(left_interval[iAxis].start, search_interval[iAxis].x);
							left_interval[iAxis].end   = min(left_interval[iAxis].end,   search_interval[iAxis].y);
						}
					}

					first = true;

					uint32 indexRight = indexLeft;

					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];						

						if (PrimitiveBI.y > s.split)
						{
							pPrimIdxW[indexRight++] = PrimitiveIndex;
							if (first)
							{
								search_interval[0] = ppBI[0][PrimitiveIndex];
								search_interval[1] = ppBI[1][PrimitiveIndex];
								search_interval[2] = ppBI[2][PrimitiveIndex];
								first = false;
							}
							else
							{
								for (int iAxis = 0; iAxis < XYZ; iAxis++)
								{
									search_interval[iAxis].x = min(search_interval[iAxis].x, ppBI[iAxis][PrimitiveIndex].x);
									search_interval[iAxis].y = max(search_interval[iAxis].y, ppBI[iAxis][PrimitiveIndex].y);
								}
							}
						}
					}

					// if first has been updated within the sorting loop 
					// maybe there is a better bounding box 
					if (!first)
					{
						// but it has to be saturated to the original bounding box
						for (int iAxis = 0; iAxis < XYZ; iAxis++)
						{
							right_interval[iAxis].start = max(right_interval[iAxis].start, search_interval[iAxis].x);
							right_interval[iAxis].end   = min(right_interval[iAxis].end,   search_interval[iAxis].y);
						}
					}

					S_TreeNode left_node(m_nPrimIdx, indexLeft, current_node_index);					
					S_TreeNode right_node(indexLeft, indexRight, current_node_index);

					pTree[m_nNode++] = left_node;
					pTree[m_nNode++] = right_node;

					pTree[current_node_index].SplitAxis(s.split, axis);

					pInterval[m_nInterval++] = left_interval[X];
					pInterval[m_nInterval++] = left_interval[Y];
					pInterval[m_nInterval++] = left_interval[Z];
					pInterval[m_nInterval++] = right_interval[X];
					pInterval[m_nInterval++] = right_interval[Y];
					pInterval[m_nInterval++] = right_interval[Z];

					m_nPrimIdx += left_node.Count() + right_node.Count();
				}
				else
				{
					pTree[current_node_index].start = m_nTreeIdx;
					pTree[current_node_index].end   = m_nTreeIdx + primitive_count;
					pTree[current_node_index].SplitAxis(0.0f, TREE_LEAF); //split = as_float(KD_LEAF);

					S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

					pTree[m_nNode++] = dummy_node; // left  child dummy
					pTree[m_nNode++] = dummy_node; // right child dummy

					for (int iInterval = 0; iInterval < 6; iInterval++)
						pInterval[m_nInterval++] = S_Interval();

					for (int iTreeIdx = current_node.start; iTreeIdx < current_node.end; iTreeIdx++)
						pTreeIdx[m_nTreeIdx++] = pPrimIdxR[iTreeIdx]+m_pIndex->Offset() / 3;

					leaf_count++; // if all nodes kick this line - next depth will not be checked
				} // if (primitive_count > 4 && SAH(EXEC_H, pInterval + current_node_index*XYZ, s, primitive_count))
			} // if ((m_nTree+m_nPrimitive+primitive_count*2 < maxPrim) && !current_node.Leaf())
			else 
			{
				leaf_count += 1;			

				S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

				pTree[m_nNode++] = dummy_node; // left  child dummy
				pTree[m_nNode++] = dummy_node; // right child dummy

				for (int iInterval = 0; iInterval < 6; iInterval++)
					pInterval[m_nInterval++] = S_Interval();
			}
		} // for (uint32 iNode = 0; iNode < node_count; iNode++)
		m_pPrimIdx->Swap();

		depth++; // increase depth level

	} // while (depth < m_nMaxDepth)
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::BVHTree_Instanced_p0()
{
	/// First init index array for root
	int * pTreeIdx  = (int *) m_pTreeIdx->hPtr();
	float4 * pActorData = (float4 *) I_SpatialTree::ActorData()->hPtr();
	
	int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
	for (int iPrim = 0; iPrim < nPrimitive(); iPrim++) pPrimIdxR[iPrim] = iPrim;
	
	float2 * ppBI[XYZ] = { (float2 * ) m_ppBoundingInterval[X]->hPtr(), 
												 (float2 * ) m_ppBoundingInterval[Y]->hPtr(), 
												 (float2 * ) m_ppBoundingInterval[Z]->hPtr() };

	/// Init Root Node
	S_TreeNode root(m_nPrimIdx, nPrimitive());

	m_nNode = m_nPrimIdx = m_nTreeIdx = m_nInterval = 0;

	S_TreeNode * pTree = (S_TreeNode *) m_pNode->hPtr();
	pTree[m_nNode++] = root;

	S_Interval * pInterval = (S_Interval *) m_pInterval->hPtr();
	pInterval[m_nInterval++] = f2(m_Box.pmin.x, m_Box.pmax.x);
	pInterval[m_nInterval++] = f2(m_Box.pmin.y, m_Box.pmax.y);
	pInterval[m_nInterval++] = f2(m_Box.pmin.z, m_Box.pmax.z);

	/// Get Maximum size of primIdx array
	int nPrimIdxSize = m_pPrimIdx->pBufferR()->Size();

	/// Try to create maxDepth levels of KdTree
	int32 depth = 0;
	int32 leaf_count = 0;
	int32 node_count = 1, node_offset = 0;

	while (depth < m_nDepth && leaf_count != node_count)
	{
		int * pPrimIdxR = (int *) m_pPrimIdx->hPtrR();
		int * pPrimIdxW = (int *) m_pPrimIdx->hPtrW();

		m_nPrimIdx = 0; // reset primitive_idx_offset		 
		leaf_count = 0; // reset leaf_count
		
		node_count = (depth > 0) ? 1 << depth : 1; // this level has this many nodes that require splitting            		
		node_offset = ((1 << (depth+1)) - 1) - node_count; // nodes for this level are located starting from this offset    

		for (int32 iNode = 0; iNode < node_count; iNode++)
		{
			int32 current_node_index = node_offset + iNode;
			S_TreeNode current_node = pTree[current_node_index];
			int32 primitive_count = current_node.end - current_node.start;

			int nWeight = 0;

			if ((m_nTreeIdx+m_nPrimIdx+primitive_count*2 < nPrimIdxSize) && !current_node.Leaf())
			{							
				S_Interval * pCurInterval = pInterval + current_node_index*XYZ;
				int * pCurPrimIdxR = pPrimIdxR + current_node.start;

				for (int iPrim = 0; iPrim < primitive_count; iPrim++)
					nWeight += pActorData[pCurPrimIdxR[iPrim]].x;

				/// Compute SAH
				S_TreeNode s;
				int32 axis = TREE_LEAF;
				int32 bin = 0;

				if (primitive_count > 1 && (depth+1<m_nDepth) && SearchSplit(ppBI, pActorData, 
																																		 pCurPrimIdxR, 
																																		 primitive_count, 
																																		 nWeight, 
																																		 pCurInterval, 
																																		 axis, bin, s))
				{
					/// For current Node set splitting plane
					pTree[current_node_index].SplitAxis(s.split, axis); // split = as_float((as_uint(s.split) & (~KD_LEAF)) | axis);
					pTree[current_node_index].left  = m_nNode;   
					pTree[current_node_index].right = m_nNode+1;

					uint32 indexLeft = m_nPrimIdx;
								
					/// Make Left and Right Intervals and insert them into intervalTree
					S_Interval left_interval[XYZ], right_interval[XYZ];						
					// copy node interval into left_interval
					left_interval[X] = pCurInterval[X]; 
					left_interval[Y] = pCurInterval[Y]; 
					left_interval[Z] = pCurInterval[Z]; 
					// copy node interval into right_interval
					right_interval[X] = pCurInterval[X]; 
					right_interval[Y] = pCurInterval[Y]; 
					right_interval[Z] = pCurInterval[Z];

					// modify left / right ends of interval on split axis
					left_interval[axis].end = s.split; 
					right_interval[axis].start = s.split; 

					// during BVH construction bounding box can be recalculated during primitive sorting					
					bool first = true;
					float2 search_interval[XYZ] = { f2(), f2(), f2() } ;
					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];							
						
						if (PrimitiveBI.x < s.split)
						{
							pPrimIdxW[indexLeft++] = PrimitiveIndex;

							// when first primitive falls into left subtree search_interval 
							// chooses it's boundaries according to this primitive and 
							// marks first as false
							if (first)
							{
								search_interval[0] = ppBI[0][PrimitiveIndex];
								search_interval[1] = ppBI[1][PrimitiveIndex];
								search_interval[2] = ppBI[2][PrimitiveIndex];
								first = false;
							}
							// if first primitive has been found bounding box should be computed
							// by taking min and max of the interval along each axis
							else
							{
								for (int iAxis = 0; iAxis < XYZ; iAxis++)
								{
									search_interval[iAxis].x = min(search_interval[iAxis].x, ppBI[iAxis][PrimitiveIndex].x);
									search_interval[iAxis].y = max(search_interval[iAxis].y, ppBI[iAxis][PrimitiveIndex].y);
								}
							}
						}
					}

					// if first has been updated within the sorting loop 
					// maybe there is a better bounding box 
					if (!first)
					{
						// but it has to be saturated to the original bounding box
						for (int iAxis = 0; iAxis < XYZ; iAxis++)
						{
							left_interval[iAxis].start = max(left_interval[iAxis].start, search_interval[iAxis].x);
							left_interval[iAxis].end   = min(left_interval[iAxis].end,   search_interval[iAxis].y);
						}
					}

					first = true;

					uint32 indexRight = indexLeft;

					for (int32 iPrim = 0; iPrim < primitive_count; iPrim++)
					{
						uint32 PrimitiveIndex = pPrimIdxR[current_node.start + iPrim];
						float2 PrimitiveBI = ppBI[axis][PrimitiveIndex];						

						if (PrimitiveBI.y > s.split)
						{
							pPrimIdxW[indexRight++] = PrimitiveIndex;

							// when first primitive falls into left subtree search_interval 
							// chooses it's boundaries according to this primitive and 
							// marks first as false
							if (first)
							{
								search_interval[0] = ppBI[0][PrimitiveIndex];
								search_interval[1] = ppBI[1][PrimitiveIndex];
								search_interval[2] = ppBI[2][PrimitiveIndex];
								first = false;
							}
							// if first primitive has been found bounding box should be computed
							// by taking min and max of the interval along each axis
							else
							{
								for (int iAxis = 0; iAxis < XYZ; iAxis++)
								{
									search_interval[iAxis].x = min(search_interval[iAxis].x, ppBI[iAxis][PrimitiveIndex].x);
									search_interval[iAxis].y = max(search_interval[iAxis].y, ppBI[iAxis][PrimitiveIndex].y);
								}
							}
						}
					}

					// if first has been updated within the sorting loop 
					// maybe there is a better bounding box 
					if (!first)
					{
						// but it has to be saturated to the original bounding box
						for (int iAxis = 0; iAxis < XYZ; iAxis++)
						{
							right_interval[iAxis].start = max(right_interval[iAxis].start, search_interval[iAxis].x);
							right_interval[iAxis].end   = min(right_interval[iAxis].end,   search_interval[iAxis].y);
						}
					}
					S_TreeNode left_node(m_nPrimIdx, indexLeft, current_node_index);					
					S_TreeNode right_node(indexLeft, indexRight, current_node_index);
	
					pTree[m_nNode++] = left_node;
					pTree[m_nNode++] = right_node;

					pTree[current_node_index].SplitAxis(s.split, axis);

					pInterval[m_nInterval++] = left_interval[X];
					pInterval[m_nInterval++] = left_interval[Y];
					pInterval[m_nInterval++] = left_interval[Z];
					pInterval[m_nInterval++] = right_interval[X];
					pInterval[m_nInterval++] = right_interval[Y];
					pInterval[m_nInterval++] = right_interval[Z];

					m_nPrimIdx += left_node.Count() + right_node.Count();
				}
				else
				{
					pTree[current_node_index].start = m_nTreeIdx;
					pTree[current_node_index].end   = m_nTreeIdx + primitive_count;
					pTree[current_node_index].SplitAxis(0.0f, TREE_LEAF);

					S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

					pTree[m_nNode++] = dummy_node; // left  child dummy
					pTree[m_nNode++] = dummy_node; // right child dummy

					for (int iInterval = 0; iInterval < 6; iInterval++)
						pInterval[m_nInterval++] = S_Interval();

					for (int iTreeIdx = current_node.start; iTreeIdx < current_node.end; iTreeIdx++)
						pTreeIdx[m_nTreeIdx++] = pPrimIdxR[iTreeIdx];

					leaf_count++; // if all nodes kick this line - next depth will not be checked
				} // if (primitive_count > 4 && SAH(EXEC_H, pInterval + current_node_index*XYZ, s, primitive_count))
			} // if ((m_nTree+m_nPrimitive+primitive_count*2 < maxPrim) && !current_node.Leaf())
			else 
			{
				leaf_count += 1;			

				S_TreeNode dummy_node(as_float(TREE_LEAF), current_node_index);  // no splitting for child nodes as well

				pTree[m_nNode++] = dummy_node; // left  child dummy
				pTree[m_nNode++] = dummy_node; // right child dummy

				for (int iInterval = 0; iInterval < 6; iInterval++)
					pInterval[m_nInterval++] = S_Interval();
			}
		} // for (uint32 iNode = 0; iNode < node_count; iNode++)
		m_pPrimIdx->Swap();

		depth++; // increase depth level
	} // while (depth < m_nMaxDepth)
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void glRender(const S_Box & box)
{
	glBegin(GL_TRIANGLES); // quick debug code

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmax.y, box.pmin.z);

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmax.y, box.pmin.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmin.z); //---------------------

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmin.x, box.pmin.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmax.z);

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmin.z); //---------------------

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmax.z);

	glVertex3f(box.pmin.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmin.y, box.pmax.z); //---------------------

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmax.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmin.z);

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmin.z);
	glVertex3f(box.pmax.x, box.pmax.y, box.pmin.z); //---------------------

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmax.x, box.pmin.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmin.y, box.pmax.z);

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmin.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmax.z); //---------------------

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmax.x, box.pmax.y, box.pmin.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmin.z);

	glVertex3f(box.pmax.x, box.pmax.y, box.pmax.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmin.z);
	glVertex3f(box.pmin.x, box.pmax.y, box.pmax.z);

	glEnd();
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void glRenderBVHTree(S_BVHNode * pBVHNode, int maxLevel, int curLevel, int nodeIdx, bool empty, int nOffset)
{
	if (curLevel < maxLevel)
	{
		S_BVHNode node = pBVHNode[nodeIdx];
		S_Box box;
		box.pmin = node.pmin;
		box.pmax = node.pmax;	

		int   axis  = node.Axis();

		if (axis != TREE_LEAF)
		{		
			// draw left
			int  lidx = nodeIdx+1;
			glRenderBVHTree(pBVHNode, maxLevel, curLevel+1, lidx, empty, nOffset);
			// draw right
			int  ridx = node.right - nOffset;
			glRenderBVHTree(pBVHNode, maxLevel, curLevel+1, ridx, empty, nOffset);
		}
		else
		{
			S_BVHNode node = pBVHNode[nodeIdx];
			glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
			if ((node.Count() != 0) || empty) glRender(box);
			glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
		}
	}
	else
	{
		S_BVHNode node = pBVHNode[nodeIdx];
		S_Box box;
		box.pmin = node.pmin;
		box.pmax = node.pmax;	

		glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
		if ((node.Count() != 0) || empty) glRender(box);
		glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
	}
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::RenderBVHTree(int maxLevel, matrix4x4 * pModel, matrix4x4 * pView, matrix4x4 * pProjection, I_api_Device * pApiDevice)
{
	matrix4x4 modelview = (*pModel) * (*pView);
	glUseProgram(0);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	glLoadMatrixf((float *) &modelview);

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glLoadMatrixf((float *) pProjection);

	glRenderBVHTree( (S_BVHNode *) m_pBVHTree->hPtr(), maxLevel, 0, 0, false, m_pBVHTree->Offset());
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void C_gl_SpatialTree::RenderBVHTreeRayTrace(float3 orig, 
																						 float3 dir, 
																						 int maxLevel, 
																						 bool empty)
{
	S_BVHNode * pNodes = (S_BVHNode *) I_SpatialTree::BVHTree()->hPtr();

	int * pTreeIdx = (int *) I_SpatialTree::TreeIdx()->hPtr();
	float4 * pActorData = (float4 *) I_SpatialTree::ActorData()->hPtr();

	int node_stack[64];

	float tnear = 0.0f, tfar = 0.0f;
	float split = 0.0f, tsplit = 0.0f;
	float thit = 3.402823466e+38F, tprev = thit;

	int stack_index = 0;
	int node_index = TREE_ROOT;

	float3 rayD = dir;
	float3 rayO = orig; 

	float3 inv_dir = 1.0f / rayD;
	int sign_dir[3] = { 0, 0, 0 }; 

	sign_dir[0] = (rayD.x >= 0) ? 1 : 0;
	sign_dir[1] = (rayD.y >= 0) ? 1 : 0;
	sign_dir[2] = (rayD.z >= 0) ? 1 : 0;

	node_stack[stack_index++] = node_index;

	while (stack_index > 0)
	{
		stack_index--;

		node_index = node_stack[stack_index];
		S_BVHNode bvh = pNodes[node_index];

		float3 pmin = bvh.pmin;
		float3 pmax = bvh.pmax;

		if (Intersect(pmin, pmax, rayO, rayD, tnear, tfar))
		{
			S_Box box(pmin, pmax);
			glColor3f(1, 0, 0);
			glRender(box);

			if (tnear < 0) tnear = 0.0f;

			if (bvh.Axis() != TREE_LEAF)
			{
				int axis = bvh.Axis();
				float split = bvh.Split();

				float o = ((float*)&rayO)[axis];
				float d = ((float*)&inv_dir)[axis];

				tsplit = (split - o) * d;

				int first_left = sign_dir[axis];
				int near, far;

				if (first_left) 
				{
					near = node_index+1;
					far = pNodes[node_index].right;
				}
				else
				{
					near = pNodes[node_index].right;
					far = node_index+1;
				}

				if(tsplit < tnear)
				{
					node_stack[stack_index++] = far;
				}
				else if (tsplit > tfar)
				{
					node_stack[stack_index++] = near;
				}
				else
				{
					node_stack[stack_index++] = far;
					node_stack[stack_index++] = near;
				}
			}
			else
			{
				int actor_start = bvh.start;
				int actor_count = bvh.Count();

				for (int iActor = 0; iActor < actor_count; iActor++)
				{
					int ActorIdx = pTreeIdx[actor_start];
				}
			}
		} // if (Intersect(pmin, pmax, rayO, rayD, tnear, tfar))
	} // while (!bHit && stack_index > 0)
}